Evolutionary algorithms (EAs) are population-based general-purposeoptimization algorithms, and have been successfully applied in variousreal-world optimization tasks. However, previous theoretical studies oftenemploy EAs with only a parent or offspring population and focus on specificproblems. Furthermore, they often only show upper bounds on the running time,while lower bounds are also necessary to get a complete understanding of analgorithm. In this paper, we analyze the running time of the($\mu$+$\lambda$)-EA (a general population-based EA with mutation only) on theclass of pseudo-Boolean functions with a unique global optimum. By applying therecently proposed switch analysis approach, we prove the lower bound $\Omega(n\ln n+ \mu + \lambda n\ln\ln n/ \ln n)$ for the first time. Particularly on thetwo widely-studied problems, OneMax and LeadingOnes, the derived lower bounddiscloses that the ($\mu$+$\lambda$)-EA will be strictly slower than the(1+1)-EA when the population size $\mu$ or $\lambda$ is above a moderate order.Our results imply that the increase of population size, while usually desiredin practice, bears the risk of increasing the lower bound of the running timeand thus should be carefully considered.
展开▼
机译：进化算法（EA）是基于种群的通用优化算法，已成功应用于各种现实世界的优化任务中。但是，以前的理论研究通常只在父母或后代的人群中使用EA，并专注于特定问题。此外，它们通常仅显示运行时间的上限，而下限对于全面了解算法也是必需的。在本文中，我们分析了（$ \ mu $ + $ \ lambda $）-EA（仅具有突变的基于总体的通用EA）在具有唯一全局最优性的伪布尔函数类上的运行时间。通过应用最近提出的开关分析方法，我们首次证明了下界$ \ Omega（n \ ln n + \ mu + \ lambda n \ ln \ ln n / \ ln n）$。特别是在两个被广泛研究的问题OneMax和LeadingOnes上，得出的下界表明，当种群大小为\\时，（$ \ mu $ + $ \ lambda $）-EA绝对比（1 + 1）-EA更慢。 mu $或$ \ lambda $处于中等水平以上。我们的结果表明，人口规模的增长虽然在实践中通常是期望的，但有增加运行时间下限的风险，因此应谨慎考虑。
展开▼
